package wangn.procedure;

import wangn.adt.CFG;
import wangn.adt.ItemSetNode;
import wangn.adt.base.More;
import wangn.adt.base.Pair;
import wangn.adt.base.Tri;
import wangn.adt.lrparsing.RootNode;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 建立LR(1)表格，因为不允许二义性文法，所以一旦检测到二义性文法就出错处理
 * 使用n叉树来表示这张表（3层），节点包括各种标识符
 *
 *  * LR(1)分析表的节点
 *  * 这样组织：
 *  * 第一层节点：是根节点，分支是各个状态，以List存储
 *  * 第二层节点：分支是各个Vt或者Vn，以Map存储
 *  * 第三层节点：保存是转移还是规约，以及后面是表示状态或者文法第几项的数字，以Node存储
 *
 * 步骤：
 * 对LRItem进行dfs，若点后面有字符就标记为转移S，否则标记为规约并且求Follow
 */
public class LRParsingTable {

    private RootNode root;
    private CFG cfg;

    private Set<Integer> visitedItem = new HashSet<>();//防止环里面循环

    public RootNode constructLRParsingTable(CFG cfg, ItemSetNode lrItemRoot){
        this.cfg = cfg;
        root = new RootNode();
        dfs(lrItemRoot);
        return root;
    }

    /**
     *
     * @function 对LR项集进行DFS，通过遍历每一个节点的每一项
     *           1、若该项产生式的右部的点后有字符，则观察孩子来确定接下来的转移
     *           2、若点后无字符，则进行FOLLOW，并填入规约
     *           3、若填入过程中发现重复表项，则记录错误（二义性文法），但是继续分析
     * @param lrItemNode 每一个lrItem
     */
    private void dfs(ItemSetNode lrItemNode){
        if (visitedItem.contains(lrItemNode.getState()))return;
        visitedItem.add(lrItemNode.getState());

        root.addChild(lrItemNode.getState());

        int length = lrItemNode.getLength();
        int idx = 0;
        while (idx < length){
            Tri<Integer, Integer, More<Character>> lrItem = lrItemNode.getItem(idx);
            String rightGrammar = cfg.getGrammar(lrItem.getFirst()).getSecond();
            if (lrItem.getSecond() >= rightGrammar.length()){//规约
                More<Character> checkFlags = lrItem.getThird();
                int charLength = checkFlags.getLength();
                for (int i = 0; i < charLength; i++){
                    char transferChar = checkFlags.getItem(i);
//                    if (root.getChild(lrItemNode.getState()).hasTransferChar(transferChar)){
//                        System.out.println("Conflict Item: in "+lrItemNode.getState()+" state, "+transferChar+" as next token.");
//                        System.out.println("Item1: "+(root.getChild(lrItemNode.getState()).getChild(transferChar).isTransfer()
//                                ?"s"
//                                :"r"
//                                +root.getChild(lrItemNode.getState()).getChild(transferChar).getState()));
//                    }
                    root.getChild(lrItemNode.getState()).addChild(checkFlags.getItem(i),false,lrItem.getFirst());
                }
            }
            idx++;
        }

        //填入移动的
        List<Character> childTransferChar = lrItemNode.getChildrenTranferChars();
        for (char transferChar : childTransferChar){
            ItemSetNode child = lrItemNode.getChild(transferChar);
            root.getChild(lrItemNode.getState()).addChild(transferChar,true,child.getState());
//            if (root.getChild(lrItemNode.getState()).hasTransferChar(transferChar)){
//                System.out.println("Conflict Item: in "+lrItemNode.getState()+" state, "+transferChar+" as next token.");
//                System.out.println("Item1: "+(root.getChild(lrItemNode.getState()).getChild(transferChar).isTransfer()
//                        ?"s"
//                        :"r"
//                        +root.getChild(lrItemNode.getState()).getChild(transferChar).getState()));
//            }
        }

        List<ItemSetNode> children  = lrItemNode.getChildren();
        for (ItemSetNode child : children){
            dfs(child);
        }
    }

}
